package leetcode.leetcode_438;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        int n = s.length();
        int m = p.length();
        HashMap<Character, Integer> sMap = new HashMap<>();
        HashMap<Character, Integer> pMap = new HashMap<>();
        if (n < m) {
            return new ArrayList<>();
        }
        ArrayList<Integer> list = new ArrayList<>();
        for (int i = 0; i < m; i++) {
            pMap.put(p.charAt(i), pMap.getOrDefault(p.charAt(i), 0) + 1);
            sMap.put(s.charAt(i), sMap.getOrDefault(s.charAt(i), 0) + 1);
        }
        if (sMap.equals(pMap)) {
            list.add(0);
        }
        int left = 0, right = m;
        while (right < n) {
            sMap.put(s.charAt(left), sMap.get(s.charAt(left)) - 1);
            if (sMap.get(s.charAt(left)) == 0) {
                sMap.remove(s.charAt(left));
            }
            sMap.put(s.charAt(right), sMap.getOrDefault(s.charAt(right), 0) + 1);
            if (sMap.equals(pMap)) {
                list.add(left+1);
            }
            left++;
            right++;
        }
        return list;
    }

}